'''
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
'''
from functools import cache
from typing import List


class Solution:

    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)

        @cache
        def f(i: int) -> int:
            if i >= n:
                return 0
            res = f(i + 1)
            for j in range(i + 1, n):
                res = max(res, f(j + 2) + prices[j] - prices[i])
            return res
        return f(0)

    def maxProfit2(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [0] * (n + 2)
        for i in range(n - 1, -1, -1):
            res = dp[i+1]
            for j in range(i + 1, n):
                res = max(res, dp[j + 2] + prices[j] - prices[i])
            dp[i] = res
        # print(dp)
        return dp[0]

    def maxProfit3(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [0] * (n+2)
        # 就一维度，依赖后方
        # dp[i] 依赖 dp[i+1],
        # dp[n+1] + prices[n-1] - prices[i]
        # dp[n] + prices[n-2] - prices[i]
        # ...
        # dp[i+4] + prices[i+2] - prices[i]
        # dp[i+3] + prices[i+1] - prices[i]
        # 在推dp[i]的时候记住max(dp[t]+prices[t]), 即可
        best = dp[n+1] + prices[n-1]
        for i in range(n - 2, -1, -1):
            dp[i] = max(dp[i+1], best - prices[i])
            best = max(best, dp[i+2] + prices[i])
        return dp[0]
